package me.chan.sort;

import static me.chan.util.SortUtil.show;
/**
 * Created by JanGin on 2017/9/20.
 */
public class HeapSort {


    private HeapSort(){}


    public static void sort(Comparable[] pq) {

        int N = pq.length;
        //use the loop to build a sorted heap
        for (int k = N / 2; k >= 1; k--) {
            sink(pq, k, N);
        }
        //sort the pq
        while (N > 1) {
            exch(pq, 1, N--);
            sink(pq ,1, N);
        }
    }

    private static void sink(Comparable[] pq, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(pq, j, j+1)) {
                j++;
            }
            if (!less(pq, k, j)) {
                break;
            }
            exch(pq, k, j);
            k = j;
        }
    }


    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }

    private static void exch(Comparable[] pq, int i, int j) {
        Comparable swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    public static void main(String[] args) {
        Integer[] arr = {20, 17, 12, 9, 10, 23, 13, 24, 19, 93, 8, 15, 98, 4, 68 };
        sort(arr);
        show(arr);
    }
}
